package net.projecteuler.prob;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

public class Problem83 implements Runnable{
	private int[][] matrix = null;
	private int[][] scoreMat = null;
	
	private static String FILE_PATH = "./res/matrix.txt";
	private static int SIZE = 80;
	private static int INF = Integer.MAX_VALUE / 2;
	private static int[] di = {-1, -1, 1, 1};
	private static int[] dj = {-1, 1, -1, 1};
	
	@Override
	public void run() {
		readMatrix();
		
		scoreMat = new int[SIZE][SIZE];
		
		for(int i = 0; i < SIZE; i++)
			for(int j = 0; j < SIZE; j++)
				scoreMat[i][j] = INF;
		scoreMat[0][0] = matrix[0][0];
		
		int trial = 1;
		while(true){
			int[][] scoreMatTemp = new int[SIZE][SIZE];
			
			for(int i = 0; i < SIZE; i++){
				for(int j = 0; j < SIZE; j++){
					int minScore = Integer.MAX_VALUE;
					
					for(int k = 0; k < 4; k++){
						int iTemp = i + di[k];
						int jTemp = j + dj[k];
						if(iTemp < 0 || iTemp >= SIZE || jTemp < 0 || jTemp >= SIZE)
							break;
						
						int score = matrix[i][j] + scoreMat[iTemp][jTemp];
						if(score < minScore)
							minScore = score;
					}
					
					if(minScore >= INF)
						scoreMatTemp[i][j] = INF;
					else
						scoreMatTemp[i][j] = minScore;
				}
			}
			
			if(checkSame(scoreMat, scoreMatTemp))
				break;
			
			scoreMat = scoreMatTemp;
			if(trial % 10000 == 0)
			System.out.println("Trial " + trial);
			trial++;
			
		}
		
		System.out.println("DONE! " + trial);
		System.out.println(scoreMat[SIZE - 1][SIZE - 1]);
		
	}
	
	private void readMatrix(){
		try {
			File file = new File(FILE_PATH);
			BufferedReader br = new BufferedReader(new FileReader(file));
			
			matrix = new int[SIZE][SIZE];
			
			for(int i = 0; i < SIZE; i++){
				String line = br.readLine();
				String[] strs = line.split(",");
				
//				matrix[i] = new int[SIZE];
				for(int j = 0; j < SIZE; j++)
					matrix[i][j] = Integer.parseInt(strs[j]);
			}
			
		} catch (IOException e) {
			e.printStackTrace();
			return;
		}
	}
	
	private boolean checkSame(int[][] arr1, int[][] arr2){
		for(int i = 0; i < SIZE; i++)
			for(int j = 0; j < SIZE; j++)
				if(arr1[i][j] != arr2[i][j])
					return false;
		return true;
	}
}
